package middle;

import java.util.ArrayList;
import java.util.List;

public class Solution_79 {

    private boolean[][] visited;
    private int row;
    private int col;

    public boolean exist(char[][] board, String word) {
        row = board.length;
        col = board[0].length;
        visited = new boolean[row][col];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                boolean dps = dps(board, word.toCharArray(), 0, i, j);
                if (dps) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dps(char[][] board, char[] chars, int charsIndex, int i, int j) {
        if (charsIndex == chars.length) {
            return true;
        }
        if (i < 0 || i >= row || j < 0 || j >= col) {
            return false;
        }
        if (visited[i][j] || board[i][j] != chars[charsIndex]) {
            return false;
        }
        visited[i][j] = true;
        boolean flag = dps(board, chars, charsIndex + 1, i + 1, j)
        || dps(board, chars, charsIndex + 1, i - 1, j)
        || dps(board, chars, charsIndex + 1, i, j + 1)
        || dps(board, chars, charsIndex + 1, i, j - 1);
        visited[i][j] = false;
        return flag;
    }

    public static void main(String[] args) {
        Solution_79 model = new Solution_79();
        System.out.println(model.exist(new char[][]{{'A','B','C','E'}, {'S','F','C','S'}, {'A','D','E','E'}}, "SEE"));
        System.out.println(model.exist(new char[][]{{'A','B','C','E'}, {'S','F','C','S'}, {'A','D','E','E'}}, "ABCB"));
    }
}
